package com.zengqingfa.algorithm.cz.chapter02;

import java.util.Arrays;

/**
 * @author zengqingfa
 * @className InsertSort
 * @description
 * @create 2021/8/6 19:41
 */
public class InsertSort {

    public static void main(String[] args) {
        Integer[] arr = {3, 1, 4, 7, 6, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] arr) {
        //待插入的元素，从索引1开始为第一个元素，总共待插入的元素为n-1
        for (int i = 1; i < arr.length; i++) {
            //从索引i处倒序比较获取待插入元素的位置
            for (int j = i; j > 0; j--) {
                if (greater(arr[j - 1], arr[j])) {
                    swap(arr, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 判断a是否比b大
     *
     * @param a
     * @param b
     * @return true or false
     */
    public static boolean greater(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    /**
     * 交换数组索引i和j位置上的元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}